﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 该数组最长严格上升子序列的长度
     * @param a int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int> a)
    {
        vector<int> dp;//dp[i]表示长度为i的子序列的结尾最小值

        for (int i = 0; i < a.size(); ++i)
        {
            if (dp.empty() || dp.back() < a[i])//dp数组没有元素或者新来的元素更大，接到dp数组后面
            {
                dp.push_back(a[i]);
            }
            else//如果新来的元素无法接到后面，采用二分查找，找到最左边比他大的值，替换，方便后面找到更长的长度，但是我们破坏了数组，该数组不是子序列的，但是没关系，只关心长度
            {
                int begin = 0, end = dp.size() - 1;
                while (begin < end)
                {
                    int mid = (begin + end) >> 1;
                    if (dp[mid] >= a[i])//缩小
                    {
                        end = mid;
                    }
                    else
                    {
                        begin = mid + 1;
                    }
                }
                dp[begin] = a[i];
            }
        }
        return dp.size();
    }
};

/*
描述
给定一个长度为 n 的数组a，求它的最长严格上升子序列的长度。
所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。
例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。
我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标
i和j 满足i<j 且ai≥aj。数据范围：0≤n≤10^5，1<=a[i]<=10^9
要求：时间复杂度O(nlogn)， 空间复杂度O(n)

示例1
输入：
[1,4,7,5,6]
返回值：
4
说明：
最长上升子序列为 [1,4,5,6] ，长度为4。
*/

